package com.cty.seventeenthDay;

import java.util.Arrays;

/*
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。
 * 该矩阵具有以下特性：每行的元素从左到右升序排列
 * 每列的元素从上到下升序排列。
 * */
public class Q_21 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        boolean ans = searchMatrix4(matrix, 5);
        System.out.println(ans);
    }

    // 超出时间限制 时间复杂度O(M + N) 时间复杂度太高
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int j = 0;
        while (j < n) {
            for (int i = 0; i < m; i++) {
                if (matrix[i][j] < target) {
                    continue;
                } else if (matrix[i][j] == target) {
                    return true;
                } else {
                    j++;
                    i = 0;
                }
            }
        }
        return false;
    }

    //方法一:直接查找 O(MN)(力扣官方题解) 过了？？？ 时间复杂度 M + N > MN ????? 我不理解 有没有大佬解释一下
    public static boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    // 方法二:二分查找(力扣官方题解)
    /*
     * 思路:
     *   由于每行的元素大小都是从小到大的 所以我们只需要对每行的数据进行二分查找即可
     *   时间复杂度O(Mlogn) 空间复杂度O(1)
     * */
    public static boolean searchMatrix3(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        for (int[] nums : matrix) {
            int index = search(nums, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }

    // 二分查找的方法
    public static int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            // 这一步是防止溢出
            int mid = (high - low) / 2 + low;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // Z字形查找
    /*
     *  思路:
     *   我们从矩阵的右上角开始寻找
     *   x为横坐标 y为纵坐标
     *   取出一个子矩阵 子矩阵的范围 左下角[x,y] 右上角 是原矩阵的右上角
     *   该子矩阵中的左上角 在上一个循环中已被判断过了  如果小于target 则x++;
     *   如果大于 target 则 y--;
     *   相等返回
     * */
    public static boolean searchMatrix4(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int n = matrix[0].length, m = matrix.length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            int num = matrix[x][y];
            if (num == target) {
                return true;
            } else if (num > target) {
                y--;
            } else {
                x++;
            }
        }
        return false;
    }


}
